{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #三角形最小路径和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumTotal"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #三角形最小路径和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个三角形 <code>triangle</code> ，找出自顶向下的最小路径和。</p>\n",
    "\n",
    "<p>每一步只能移动到下一行中相邻的结点上。<strong>相邻的结点 </strong>在这里指的是 <strong>下标</strong> 与 <strong>上一层结点下标</strong> 相同或者等于 <strong>上一层结点下标 + 1</strong> 的两个结点。也就是说，如果正位于当前行的下标 <code>i</code> ，那么下一步可以移动到下一行的下标 <code>i</code> 或 <code>i + 1</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]\n",
    "<strong>输出：</strong>11\n",
    "<strong>解释：</strong>如下面简图所示：\n",
    "   <strong>2</strong>\n",
    "  <strong>3</strong> 4\n",
    " 6 <strong>5</strong> 7\n",
    "4 <strong>1</strong> 8 3\n",
    "自顶向下的最小路径和为&nbsp;11（即，2&nbsp;+&nbsp;3&nbsp;+&nbsp;5&nbsp;+&nbsp;1&nbsp;= 11）。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>triangle = [[-10]]\n",
    "<strong>输出：</strong>-10\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= triangle.length &lt;= 200</code></li>\n",
    "\t<li><code>triangle[0].length == 1</code></li>\n",
    "\t<li><code>triangle[i].length == triangle[i - 1].length + 1</code></li>\n",
    "\t<li><code>-10<sup>4</sup> &lt;= triangle[i][j] &lt;= 10<sup>4</sup></code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>你可以只使用 <code>O(n)</code>&nbsp;的额外空间（<code>n</code> 为三角形的总行数）来解决这个问题吗？</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 120&nbsp;题相同：&nbsp;<a href=\"https://leetcode-cn.com/problems/triangle/\">https://leetcode-cn.com/problems/triangle/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [IlPe0q](https://leetcode.cn/problems/IlPe0q/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [IlPe0q](https://leetcode.cn/problems/IlPe0q/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[2],[3,4],[6,5,7],[4,1,8,3]]', '[[-10]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        dp1 = [triangle[0][0]]\n",
    "        dp2 = []\n",
    "\n",
    "        for layer in triangle[1:]:\n",
    "            dp2.append(dp1[0] + layer[0])\n",
    "            \n",
    "            for i in range(1, len(layer) - 1):\n",
    "                dp2.append(min(dp1[i], dp1[i - 1]) + layer[i])\n",
    "\n",
    "            dp2.append(dp1[-1] + layer[-1])\n",
    "\n",
    "            dp1 = dp2\n",
    "            dp2 = []\n",
    "        return min(dp1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        m=len(triangle)\n",
    "        dp = [[0] * m for _ in range(m)]\n",
    "        dp[0][0]=triangle[0][0]\n",
    "\n",
    "\n",
    "        for i in range(1,m):\n",
    "            dp[i][0]=dp[i-1][0]+triangle[i][0]\n",
    "\n",
    "        for i in range(1,m):\n",
    "            dp[i][i]=dp[i-1][i-1]+triangle[i][i]\n",
    "        \n",
    "        for i in range(1,m):\n",
    "            for j in range(1,i):\n",
    "                dp[i][j]=min(dp[i-1][j],dp[i-1][j-1])+triangle[i][j]\n",
    "\n",
    "        return min(dp[-1])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        dp = triangle[-1]\n",
    "        for i in range(len(triangle) - 2, -1, -1):\n",
    "            for j in range(len(triangle[i])):\n",
    "                dp[j] = triangle[i][j] + min(dp[j],dp[j + 1])\n",
    "        return dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        n = len(triangle)\n",
    "        min_road = [0] * n\n",
    "        min_road[0] = triangle[0][0]\n",
    "        tmp = min_road[:]\n",
    "        for i in range(1, n):\n",
    "            tmp = min_road[:]\n",
    "            min_road[0] = triangle[i][0] + tmp[0]\n",
    "            for j in range(1, i):\n",
    "                min_road[j] = triangle[i][j] + min(tmp[j-1], tmp[j])\n",
    "            min_road[i] = triangle[i][i] + tmp[i-1] \n",
    "        return min(min_road)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        n = len(triangle)\n",
    "        cur = triangle[0]\n",
    "        for i in range(n-1):\n",
    "            nxt = [float('inf')] * (i+2)\n",
    "            for j, num in enumerate(cur):\n",
    "                nxt[j] = min(nxt[j], num+triangle[i+1][j])\n",
    "                nxt[j+1] = min(nxt[j+1], num+triangle[i+1][j+1])\n",
    "            cur = nxt\n",
    "        return min(cur)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "#         n = len(triangle)\n",
    "#         pre = triangle[0]\n",
    "#         for i in range(1, n):\n",
    "#             dp = []\n",
    "#             for j in range(i+1):\n",
    "#                 if j == 0: dp.append(pre[0] + triangle[i][0])\n",
    "#                 elif j == i: dp.append(pre[j-1] + triangle[i][j])\n",
    "#                 else:\n",
    "#                     dp.append(min(pre[j-1], pre[j]) + triangle[i][j])\n",
    "#             pre = dp\n",
    "#         return min(pre)\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        n = len(triangle)\n",
    "        f = [0]*n\n",
    "        f[0] = triangle[0][0]\n",
    "        for i in range(1, n):\n",
    "            f[i] = f[i-1] + triangle[i][i]   # 更新第i层最右节点\n",
    "            for j in range(i-1, 0, -1):\n",
    "                f[j] = min(f[j-1], f[j]) + triangle[i][j]   # 更新中间节点，此时j-1和j表示的是第i-1层的节点\n",
    "            f[0] = f[0] + triangle[i][0]   # 更新第i层最左节点\n",
    "        return min(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        n = len(triangle)\n",
    "        f = [inf] * n\n",
    "        f[0] = 0\n",
    "        for i in range(n):\n",
    "            for j in range(len(triangle[i]) - 1, -1, -1):\n",
    "                if j == 0:\n",
    "                    f[0] += triangle[i][j]\n",
    "                else:\n",
    "                    f[j] = min(f[j-1], f[j]) + triangle[i][j]\n",
    "        return min(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        n = len(triangle)\n",
    "        f = [[0] * n for _ in range(n)]\n",
    "        f[0][0] = triangle[0][0]\n",
    "        for i in range(1, n):\n",
    "            f[i][0] = f[i - 1][0] + triangle[i][0]\n",
    "            for j in range(1, i):\n",
    "                f[i][j] = min(f[i - 1][j], f[i - 1][j - 1]) + triangle[i][j]\n",
    "            f[i][i] = f[i - 1][i - 1] + triangle[i][i]\n",
    "        return min(f[n - 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "\n",
    "        dp = triangle[-1]\n",
    "        for i in range(len(triangle)-2,-1,-1):\n",
    "            for j in range(i+1):\n",
    "                dp[j] = min(dp[j],dp[j+1])+triangle[i][j]\n",
    "        return dp[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        n = len(triangle)\n",
    "        f = [0] * n\n",
    "        f[0] = triangle[0][0]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            f[i] = f[i - 1] + triangle[i][i]\n",
    "            for j in range(i - 1, 0, -1):\n",
    "                f[j] = min(f[j - 1], f[j]) + triangle[i][j]\n",
    "            f[0] += triangle[i][0]\n",
    "        \n",
    "        return min(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        s = [0] * len(triangle[-1])\n",
    "        s[0] = triangle[0][0]\n",
    "        for i in range(1, len(triangle)):\n",
    "            s[i] = triangle[i][-1] + s[i-1]\n",
    "            for j in range(i-1, 0, -1):\n",
    "                s[j] = triangle[i][j] + min(s[j], s[j-1])\n",
    "            s[0] += triangle[i][0]\n",
    "        #print(s)\n",
    "        return min(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        m = len(triangle)\n",
    "        dp = [float(\"inf\") for _ in range(m)]\n",
    "\n",
    "        dp[0] = triangle[0][0]\n",
    "\n",
    "        for i in range(1, m):\n",
    "            n = len(triangle[i])\n",
    "            for j in range(n-1, 0, -1):\n",
    "                dp[j] = triangle[i][j] + min(dp[j], dp[j-1])\n",
    "            dp[0] = triangle[i][0] + dp[0]\n",
    "\n",
    "        return min(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        dp = [triangle[0][0]]\n",
    "        n = len(triangle)\n",
    "        for i in range(1, n):\n",
    "            dp.append(10 ** 8)\n",
    "            for j in range(i, 0, -1):\n",
    "                dp[j] = min(dp[j], dp[j-1] + triangle[i][j])\n",
    "                dp[j-1] += triangle[i][j-1]\n",
    "        return min(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    Let dist[i][j] denotes the minimum path sum from top to the number at row i, column j. \n",
    "    dist[i][j] = triangle[i][j] + min(dist[i-1][j-1], dist[i-1][j]). \n",
    "    Since dist[j] is calculated using dist[j-1] and dist[j] from the previous row, we can reduce the space complexity to O(n) if we traverse j in the reverse order. \n",
    "    Let n be the number of rows in the triangle. \n",
    "    Time complexity: O(n^2). Space complexity: O(n). \n",
    "    '''\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        dist = [-1 for _ in range(len(triangle))]\n",
    "        for i in range(0, len(triangle)):\n",
    "            rowLen = i + 1\n",
    "            for j in range(rowLen-1, -1, -1): \n",
    "                if i == 0:\n",
    "                    dist[j] = triangle[i][j]\n",
    "                elif j == 0:\n",
    "                    dist[j] = triangle[i][j] + dist[j]\n",
    "                elif j == rowLen - 1:\n",
    "                    dist[j] = triangle[i][j] + dist[j-1]\n",
    "                else:\n",
    "                    dist[j] = triangle[i][j] + min(dist[j-1], dist[j])\n",
    "        return min(dist)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        n = len(triangle)\n",
    "        result = [0] * n\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(i, -1, -1):\n",
    "                if j == i:\n",
    "                    result[j] = result[j - 1] + triangle[i][j]\n",
    "                elif j == 0:\n",
    "                    result[j] = result[j] + triangle[i][j]\n",
    "                else:\n",
    "                    result[j] = min(result[j - 1], result[j]) + triangle[i][j]\n",
    "        \n",
    "\n",
    "        return min(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "\n",
    "        n = len(triangle)\n",
    "        dp = [0] * n\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(i,-1,-1):\n",
    "                if j == 0:\n",
    "                    dp[0]= dp[0]+triangle[i][0]\n",
    "                elif j == i:\n",
    "                    dp[j] = dp[j-1] + triangle[i][j]\n",
    "                else:\n",
    "                    dp[j] = min(dp[j],dp[j-1]) + triangle[i][j]\n",
    "\n",
    "        return min(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        n = len(triangle)\n",
    "        f = [0] * n\n",
    "        f[0] = triangle[0][0]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            f[i] = f[i - 1] + triangle[i][i]\n",
    "            for j in range(i - 1, 0, -1):\n",
    "                f[j] = min(f[j - 1], f[j]) + triangle[i][j]\n",
    "            f[0] += triangle[i][0]\n",
    "        \n",
    "        return min(f)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "            # 初始化 dp 为三角形的最后一行\n",
    "        dp = triangle[-1]\n",
    "        \n",
    "        # 从三角形的倒数第二行开始向上计算每一行的最小路径和\n",
    "        for i in range(len(triangle) - 2, -1, -1):\n",
    "            for j in range(len(triangle[i])):\n",
    "                # 更新当前行的每个元素为其最小路径和\n",
    "                dp[j] = triangle[i][j] + min(dp[j], dp[j + 1])\n",
    "\n",
    "        return dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        lenth1=len(triangle)\n",
    "        if lenth1==1:\n",
    "            return triangle[0][0]\n",
    "        lenth2=len(triangle[lenth1-2])\n",
    "        for i in range(lenth2):\n",
    "            triangle[lenth1-2][i]=min(triangle[lenth1-1][i+1],triangle[lenth1-1][i])+triangle[lenth1-2][i]\n",
    "        triangle.pop()\n",
    "        return self.minimumTotal(triangle)\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "\n",
    "        for i,v in enumerate(triangle):\n",
    "            if i==0:\n",
    "                dp=[v[0]]\n",
    "            else:\n",
    "                ndp=v[:]\n",
    "                for j in range(i+1):\n",
    "                    if j==0:\n",
    "                        ndp[j]+=dp[j]\n",
    "                    elif j==i:\n",
    "                        ndp[j]+=dp[j-1]\n",
    "                    else:\n",
    "                        ndp[j]+=min(dp[j],dp[j-1])\n",
    "                dp=ndp\n",
    "        return min(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        dp = [triangle[0][0]]\n",
    "        n = len(triangle)\n",
    "        for i in range(1, n):\n",
    "            dp.append(10 ** 8)\n",
    "            for j in range(i, 0, -1):\n",
    "                dp[j] = min(dp[j], dp[j-1] + triangle[i][j])\n",
    "                dp[j-1] += triangle[i][j-1]\n",
    "        return min(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        n = len(triangle)\n",
    "        if n == 1:\n",
    "            return triangle[0][0]\n",
    "        dp = [[0]*n for _ in range(2)]\n",
    "        dp[0][0] = triangle[0][0]\n",
    "        dp[1][0] = triangle[0][0] + triangle[1][0]\n",
    "        dp[1][1] = triangle[0][0] + triangle[1][1]\n",
    "        for i in range(2, n):\n",
    "            start, prev = i % 2, (i + 1) % 2\n",
    "            dp[start][0] = dp[prev][0] + triangle[i][0]\n",
    "            dp[start][i] = dp[prev][i-1] + triangle[i][i]\n",
    "            for j in range(1, i):\n",
    "                dp[start][j] = min(dp[prev][j],dp[prev][j-1]) + triangle[i][j]\n",
    "        return min(dp[1][0],dp[1][1]) if n == 2 else min(dp[start][j] for j in range(n))\n",
    "\n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        n = len(triangle)\n",
    "        if n == 1:\n",
    "            return triangle[0][0]\n",
    "        f = [[triangle[0][0]], []]\n",
    "        for i in range(1, n):\n",
    "            target = i % 2\n",
    "            source = 1 - target\n",
    "            f[target] = [triangle[i][0] + f[source][0]] + [\n",
    "                triangle[i][j] + min(f[source][j - 1], f[source][j])\n",
    "                for j in range(1, i)\n",
    "            ] + [triangle[i][-1] + f[source][-1]]\n",
    "        return min(f[target])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        n = len(triangle)\n",
    "        dp = triangle[:]\n",
    "\n",
    "        for i in range(1,n):\n",
    "            for j in range(i+1):\n",
    "                if j == 0:\n",
    "                    dp[i][j] = dp[i-1][j] + triangle[i][j]\n",
    "                elif j == i:\n",
    "                    dp[i][j] = dp[i-1][j-1] + triangle[j][j]\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i-1][j-1],dp[i-1][j]) + triangle[i][j]\n",
    "        return min(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        a = len(triangle)\n",
    "        dp = triangle\n",
    "        # dp = [[0 for j in range(i+1)] for i in range(a)]\n",
    "        # dp[0][0] = c[0][0]\n",
    "        m = dp[0][0]\n",
    "        n = 1\n",
    "        for i in range(1,a):\n",
    "            n +=1\n",
    "            for j in range(n):\n",
    "                if j == 0:\n",
    "                    dp[i][j] = dp[i-1][j] + dp[i][j]\n",
    "                    m = dp[i][j]\n",
    "                elif j == (len(dp[i][:])-1):\n",
    "                    dp[i][j] = dp[i-1][j-1] +dp[i][j]\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i-1][j-1]+dp[i][j],dp[i-1][j] +dp[i][j])\n",
    "                m = min(m,dp[i][j])\n",
    "        return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        a = len(triangle)\n",
    "        dp = triangle\n",
    "        # dp = [[0 for j in range(i+1)] for i in range(a)]\n",
    "        # dp[0][0] = c[0][0]\n",
    "        m = dp[0][0]\n",
    "        n = 1\n",
    "        for i in range(1,a):\n",
    "            n +=1\n",
    "            for j in range(n):\n",
    "                if j == 0:\n",
    "                    dp[i][j] = dp[i-1][j] + dp[i][j]\n",
    "                    m = dp[i][j]\n",
    "                elif j == (len(dp[i][:])-1):\n",
    "                    dp[i][j] = dp[i-1][j-1] +dp[i][j]\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i-1][j-1]+dp[i][j],dp[i-1][j] +dp[i][j])\n",
    "                m = min(m,dp[i][j])\n",
    "        return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        n = len(triangle)\n",
    "        for i in range(n-2, -1, -1):\n",
    "            for j in range(i+1):\n",
    "                triangle[i][j] += min(triangle[i+1][j], triangle[i+1][j+1])\n",
    "        return triangle[0][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        for i in range(len(triangle)):\n",
    "            for j in range(len(triangle[i])):\n",
    "                if i == 0 and j == 0:\n",
    "                    continue\n",
    "                elif j == 0:\n",
    "                    triangle[i][j] += triangle[i - 1][j]\n",
    "                elif j == i:\n",
    "                    triangle[i][j] += triangle[i - 1][j - 1]\n",
    "                else:\n",
    "                    triangle[i][j] += min(triangle[i - 1][j], triangle[i - 1][j - 1])\n",
    "        return min(triangle[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        a = len(triangle)\n",
    "        # dp = triangle\n",
    "        m = triangle[0][0]\n",
    "        n = 1\n",
    "        for i in range(1,a):\n",
    "            n +=1\n",
    "            for j in range(n):\n",
    "                if j == 0:\n",
    "                    triangle[i][j] = triangle[i-1][j] + triangle[i][j]\n",
    "                    m = triangle[i][j]\n",
    "                elif j == (len(triangle[i][:])-1):\n",
    "                    triangle[i][j] = triangle[i-1][j-1] +triangle[i][j]\n",
    "                else:\n",
    "                    triangle[i][j] = min(triangle[i-1][j-1]+triangle[i][j],triangle[i-1][j] +triangle[i][j])\n",
    "                m = min(m,triangle[i][j])\n",
    "        return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        dp=triangle[:]\n",
    "\n",
    "        for i in range(1,len(triangle)):\n",
    "            for j in range(len(triangle[i])):\n",
    "                if j==0:\n",
    "                    dp[i][j]=dp[i-1][j]+triangle[i][j]\n",
    "                elif j==len(triangle[i])-1:\n",
    "                    #print(i,j)\n",
    "                    dp[i][j]=dp[i-1][j-1]+triangle[i][j]\n",
    "                else:\n",
    "                    dp[i][j]=min(dp[i-1][j],dp[i-1][j-1])+triangle[i][j]\n",
    "        return min(dp[-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        for i in range(1,len(triangle)):\n",
    "            triangle[i][0] += triangle[i-1][0]\n",
    "            for j in range(1,len(triangle[i])-1):\n",
    "                triangle[i][j] += min(triangle[i-1][j],triangle[i-1][j-1])\n",
    "            triangle[i][len(triangle[i])-1] += triangle[i-1][len(triangle[i])-2]\n",
    "        return min(triangle[-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        a = len(triangle)\n",
    "        # dp = triangle\n",
    "        m = triangle[0][0]\n",
    "        n = 1\n",
    "        for i in range(1,a):\n",
    "            n +=1\n",
    "            for j in range(n):\n",
    "                if j == 0:\n",
    "                    triangle[i][j] = triangle[i-1][j] + triangle[i][j]\n",
    "                    m = triangle[i][j]\n",
    "                elif j == (len(triangle[i][:])-1):\n",
    "                    triangle[i][j] = triangle[i-1][j-1] +triangle[i][j]\n",
    "                else:\n",
    "                    triangle[i][j] = min(triangle[i-1][j-1]+triangle[i][j],triangle[i-1][j] +triangle[i][j])\n",
    "                m = min(m,triangle[i][j])\n",
    "        return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        a = len(triangle)\n",
    "        dp = triangle\n",
    "        # dp = [[0 for j in range(i+1)] for i in range(a)]\n",
    "        # dp[0][0] = c[0][0]\n",
    "        m = dp[0][0]\n",
    "        n = 1\n",
    "        for i in range(1,a):\n",
    "            n +=1\n",
    "            for j in range(n):\n",
    "                if j == 0:\n",
    "                    dp[i][j] = dp[i-1][j] + dp[i][j]\n",
    "                    m = dp[i][j]\n",
    "                elif j == (len(dp[i][:])-1):\n",
    "                    dp[i][j] = dp[i-1][j-1] +dp[i][j]\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i-1][j-1]+dp[i][j],dp[i-1][j] +dp[i][j])\n",
    "                m = min(m,dp[i][j])\n",
    "        return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        for i in range(1, len(triangle)):\n",
    "            t1 = triangle[i-1]\n",
    "            t2 = triangle[i]\n",
    "            for j in range(len(t2)):\n",
    "                if j==0:\n",
    "                    t2[j] += t1[j]\n",
    "                else:\n",
    "                    if j<len(t1):\n",
    "                        t2[j] += min(t1[j], t1[j-1])\n",
    "                    else:\n",
    "                        t2[j] += t1[j-1]\n",
    "            #print(triangle)\n",
    "        return min(triangle[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        m = len(triangle)\n",
    "        for i in range(m - 2, -1, -1):\n",
    "            for j in range(i + 1):\n",
    "                triangle[i][j] += min(triangle[i + 1][j], triangle[i + 1][j + 1])\n",
    "        \n",
    "        return triangle[0][0]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # n = len(triangle)\n",
    "        # dp = [[0] * (i + 1) for i in range(n)]\n",
    "\n",
    "        # dp[-1] = triangle[-1]\n",
    "\n",
    "        # for i in range(n - 2, -1, -1):\n",
    "        #     for j in range(i + 1):\n",
    "        #         dp[i][j] = min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle[i][j]\n",
    "        \n",
    "        # return dp[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        n = len(triangle)\n",
    "        for i in range(1, n):\n",
    "            triangle[i][0] += triangle[i-1][0]\n",
    "            triangle[i][-1] += triangle[i-1][-1]\n",
    "        for i in range(1, n):\n",
    "            for j in range(1, i):\n",
    "                triangle[i][j] += min(triangle[i-1][j-1], triangle[i-1][j])\n",
    "        #print(f'triangle = {triangle}')\n",
    "        \n",
    "        return min(triangle[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "\n",
    "        for i in range(1, len(triangle)):\n",
    "            for j in range(len(triangle[i])):\n",
    "                if j == 0:\n",
    "                    triangle[i][j] += triangle[i-1][0]\n",
    "                elif j == len(triangle[i])-1:\n",
    "                    triangle[i][j] += triangle[i-1][-1]\n",
    "                else:\n",
    "                    triangle[i][j] += min(triangle[i-1][j-1], triangle[i-1][j])\n",
    "        \n",
    "        return min(triangle[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        a = len(triangle)\n",
    "        dp = triangle\n",
    "        m = dp[0][0]\n",
    "        n = 1\n",
    "        for i in range(1,a):\n",
    "            n +=1\n",
    "            for j in range(n):\n",
    "                if j == 0:\n",
    "                    dp[i][j] = dp[i-1][j] + dp[i][j]\n",
    "                    m = dp[i][j]\n",
    "                elif j == (len(dp[i][:])-1):\n",
    "                    dp[i][j] = dp[i-1][j-1] +dp[i][j]\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i-1][j-1]+dp[i][j],dp[i-1][j] +dp[i][j])\n",
    "                m = min(m,dp[i][j])\n",
    "        return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        n=len(triangle)\n",
    "        triangle.reverse()\n",
    "        dp=triangle.copy()\n",
    "        #print(dp)\n",
    "        for i  in range(1,n):\n",
    "            for j in range(len(dp[i])):\n",
    "                dp[i][j]=min(dp[i-1][j],dp[i-1][j+1])+triangle[i][j]\n",
    "        #print(dp)\n",
    "        return dp[-1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        dp = [[99999] * i for i in range(1, len(triangle)+1)]\n",
    "        dp[0][0] = triangle[0][0]\n",
    "        for i in range(len(triangle)-1):\n",
    "            for j in range(len(triangle[i])):\n",
    "                dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j]+triangle[i+1][j+1])\n",
    "                dp[i+1][j] = min(dp[i+1][j], dp[i][j]+triangle[i+1][j])\n",
    "        return min(dp[-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        n = len(triangle)\n",
    "        dp = [[0] * i for i in range(1, n + 1)]\n",
    "        dp[0][0] = triangle[0][0]\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            dp[i][0] = dp[i - 1][0] + triangle[i][0]\n",
    "            for j in range(1, i):\n",
    "                dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1]) + triangle[i][j]\n",
    "            dp[i][i] = dp[i - 1][ i - 1] + triangle[i][i]\n",
    "        \n",
    "        return min(dp[n - 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        dp = [[99999] * i for i in range(1, len(triangle)+1)]\n",
    "        dp[0][0] = triangle[0][0]\n",
    "        for i in range(len(triangle)-1):\n",
    "            for j in range(len(triangle[i])):\n",
    "                dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j]+triangle[i+1][j+1])\n",
    "                dp[i+1][j] = min(dp[i+1][j], dp[i][j]+triangle[i+1][j])\n",
    "        return min(dp[-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle):\n",
    "\n",
    "        def dp(n):\n",
    "            if n == 1:\n",
    "                return triangle[0][0]\n",
    "            else:\n",
    "                listA = triangle.pop()\n",
    "                listB = triangle.pop()\n",
    "                list_c = []\n",
    "                for i in range(len(listB)):\n",
    "                    list_c.append(listB[i]+min(listA[i],listA[i+1]))\n",
    "                triangle.append(list_c)\n",
    "                dp(n-1)\n",
    "        \n",
    "        n = len(triangle)\n",
    "        dp(n)\n",
    "        \n",
    "        return triangle[0][0]\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        dp = [[99999] * i for i in range(1, len(triangle)+1)]\n",
    "        dp[0][0] = triangle[0][0]\n",
    "        for i in range(len(triangle)-1):\n",
    "            for j in range(len(triangle[i])):\n",
    "                dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j]+triangle[i+1][j+1])\n",
    "                dp[i+1][j] = min(dp[i+1][j], dp[i][j]+triangle[i+1][j])\n",
    "        return min(dp[-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        # if len(triangle)==1:\n",
    "        #     return triangle[0][0]\n",
    "        dp=[ [0]*n for n in range(1, len(triangle) + 1)]\n",
    "        dp[0][0]=triangle[0][0]\n",
    "        for i in range(1,len(triangle)):\n",
    "            dp[i][0]=dp[i-1][0]+triangle[i][0]\n",
    "            dp[i][-1]=dp[i-1][-1]+triangle[i][-1]\n",
    "        for i in range(1,len(triangle)):\n",
    "            for j in range(1,i):\n",
    "                dp[i][j]=min(dp[i-1][j],dp[i-1][j-1])+triangle[i][j]\n",
    "        return min(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        n = len(triangle)\n",
    "        dp = [[0 for _ in range(i+1)] for i in range(n)]\n",
    "        dp[0][0] = triangle[0][0]\n",
    "\n",
    "        for i in range(1,n):\n",
    "            for j in range(i+1):\n",
    "                if j == 0:\n",
    "                    dp[i][j] = dp[i-1][j] + triangle[i][j]\n",
    "                elif j == i:\n",
    "                    dp[i][j] = dp[i-1][j-1] + triangle[i][j]\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]\n",
    "        \n",
    "        return min(dp[n-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        # if j == 0: dp[i][0] = dp[i-1][0] + triangle[i-1][0]\n",
    "        # dp[i][j] = min(dp[i-1][j-1]+triangle[i][j],dp[i-1][j]+triangle[i][j])\n",
    "        dp = []\n",
    "        for i in range(len(triangle)):\n",
    "            row = []\n",
    "            for j in range(len(triangle[i])):\n",
    "                if j == 0 and i == 0:\n",
    "                    row.append(triangle[0][0])\n",
    "                elif j == 0 and i != 0:\n",
    "                    row.append(dp[i-1][0] + triangle[i][0])\n",
    "                elif j == len(triangle[i])-1 and i != 0:\n",
    "                    row.append(dp[i-1][len(triangle[i])-2] + triangle[i][len(triangle[i])-1])\n",
    "                else:\n",
    "                    row.append(min(dp[i-1][j-1]+triangle[i][j],dp[i-1][j]+triangle[i][j]))\n",
    "            dp.append(row)\n",
    "        return min(dp[len(triangle)-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        dp = [[99999] * i for i in range(1, len(triangle)+1)]\n",
    "        dp[0][0] = triangle[0][0]\n",
    "        for i in range(len(triangle)-1):\n",
    "            for j in range(len(triangle[i])):\n",
    "                dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j]+triangle[i+1][j+1])\n",
    "                dp[i+1][j] = min(dp[i+1][j], dp[i][j]+triangle[i+1][j])\n",
    "        return min(dp[-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        n=len(triangle)\n",
    "        dp = [[0] * i for i in range(1, n + 1)]\n",
    "        for u in range(n):\n",
    "            dp[n-1][u]=triangle[n-1][u]\n",
    "        if n>=2:\n",
    "            for j in range(n-2,-1,-1):\n",
    "                for k in range(j+1):\n",
    "                    dp[j][k]=triangle[j][k]+min(dp[j+1][k],dp[j+1][k+1])\n",
    "        return dp[0][0]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        if len(triangle) == 1:\n",
    "            return triangle[0][0]\n",
    "\n",
    "        n = len(triangle)\n",
    "        dp = [[0] * len(triangle[i]) for i in range(n)]\n",
    "\n",
    "        for i in range(n):\n",
    "            if i == 0:\n",
    "                dp[i][0] = triangle[i][0]\n",
    "            else:\n",
    "                dp[i][0] = dp[i-1][0] + triangle[i][0]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            for j in range(1, len(triangle[i])):\n",
    "                if j == len(triangle[i]) - 1:\n",
    "                    dp[i][j] = dp[i-1][j-1] + triangle[i][j]\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i-1][j], dp[i-1][j-1]) + triangle[i][j]\n",
    "\n",
    "        res = dp[n-1][0]\n",
    "        for j in range(1, len(triangle[n-1])):\n",
    "            res = min(res, dp[n-1][j])\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        dp = [[99999] * i for i in range(1, len(triangle)+1)]\n",
    "        dp[0][0] = triangle[0][0]\n",
    "        for i in range(len(triangle)-1):\n",
    "            for j in range(len(triangle[i])):\n",
    "                dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j]+triangle[i+1][j+1])\n",
    "                dp[i+1][j] = min(dp[i+1][j], dp[i][j]+triangle[i+1][j])\n",
    "        return min(dp[-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        dp = [[99999] * i for i in range(1, len(triangle)+1)]\n",
    "        dp[0][0] = triangle[0][0]\n",
    "        for i in range(len(triangle)-1):\n",
    "            for j in range(len(triangle[i])):\n",
    "                dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j]+triangle[i+1][j+1])\n",
    "                dp[i+1][j] = min(dp[i+1][j], dp[i][j]+triangle[i+1][j])\n",
    "        return min(dp[-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        # if j == 0: dp[i][0] = dp[i-1][0] + triangle[i-1][0]\n",
    "        # dp[i][j] = min(dp[i-1][j-1]+triangle[i][j],dp[i-1][j]+triangle[i][j])\n",
    "        dp = []\n",
    "        for i in range(len(triangle)):\n",
    "            row = []\n",
    "            for j in range(len(triangle[i])):\n",
    "                if j == 0 and i == 0:\n",
    "                    row.append(triangle[0][0])\n",
    "                elif j == 0 and i != 0:\n",
    "                    row.append(dp[i-1][0] + triangle[i][0])\n",
    "                elif j == len(triangle[i])-1 and i != 0:\n",
    "                    row.append(dp[i-1][len(triangle[i])-2] + triangle[i][len(triangle[i])-1])\n",
    "                else:\n",
    "                    row.append(min(dp[i-1][j-1]+triangle[i][j],dp[i-1][j]+triangle[i][j]))\n",
    "            dp.append(row)\n",
    "        return min(dp[len(triangle)-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        n=len(triangle[-1])\n",
    "        dp=[[float('inf')]*n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(i+1):\n",
    "                if i==0 and j==0:\n",
    "                    dp[i][j]=triangle[0][0]\n",
    "                else:\n",
    "                    dp[i][j]=triangle[i][j]+min(dp[i-1][j],dp[i-1][j-1])\n",
    "        return min(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        res = [0]\n",
    "        m, n = len(triangle), len(triangle[-1])\n",
    "        dp = [[float(inf)] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            dp[i][0] = triangle[i][0]\n",
    "        for i in range(1, m):\n",
    "            for j in range(i+1):\n",
    "                dp[i][j] = min(dp[i-1][j], dp[i-1][j-1]) + triangle[i][j]\n",
    "        return min(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        m = len(triangle)\n",
    "        n = len(triangle[m - 1])\n",
    "\n",
    "        dp = [[100000] * n for _ in range(m)]\n",
    "        dp[0][0] = triangle[0][0]\n",
    "        for i in range(1, len(triangle)):\n",
    "            for j in range(len(triangle[i])):\n",
    "                if j - 1 >= 0:\n",
    "                    dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1]) + triangle[i][j]\n",
    "                else:\n",
    "                    dp[i][j] = dp[i - 1][j] + triangle[i][j]\n",
    "\n",
    "        # print(dp)\n",
    "        ans = 1000000\n",
    "        for i in range(n):\n",
    "            ans = min(ans, dp[m - 1][i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        n = len(triangle)\n",
    "        dp = [[0]*n for _ in range(n)]\n",
    "        dp[0][0] = triangle[0][0]\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            dp[i][0] = dp[i-1][0] + triangle[i][0]\n",
    "            dp[i][i] = dp[i-1][i-1] + triangle[i][i]\n",
    "            for j in range(1, i):\n",
    "                dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]\n",
    "        \n",
    "        return min(dp[n-1])\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        n = len(triangle)\n",
    "        f = [[0] * n for _ in range(n)]\n",
    "        f[0][0] = triangle[0][0]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            f[i][0] = f[i - 1][0] + triangle[i][0]\n",
    "            for j in range(1, i):\n",
    "                f[i][j] = min(f[i - 1][j - 1], f[i - 1][j]) + triangle[i][j]\n",
    "            f[i][i] = f[i - 1][i - 1] + triangle[i][i]\n",
    "        \n",
    "        return min(f[n - 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        # dp[i][j] = min(dp[i-1][j - 1] + nums[i][j - 1], dp[i-1][j] + nums[i][j])\n",
    "        nums = triangle\n",
    "        n = len(nums)\n",
    "        dp = [[0 for i in range(n)] for i in range(n)]\n",
    "        dp[0][0] = nums[0][0]\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            dp[i][0] = dp[i-1][0] + nums[i][0]\n",
    "            for j in range(1, i):\n",
    "                dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + nums[i][j]\n",
    "            dp[i][i] = dp[i-1][i - 1] + nums[i][i]\n",
    "        \n",
    "        return min(dp[n-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        n=len(triangle)\n",
    "        #填一个下三角形\n",
    "        dp=[[0 for _ in range(n)] for _ in range(n)]\n",
    "        dp[0][0]=triangle[0][0]\n",
    "        for i in range(1,n):\n",
    "            dp[i][0]=dp[i-1][0]+triangle[i][0]\n",
    "            for j in range(1,i):\n",
    "                dp[i][j]=min(dp[i-1][j],dp[i-1][j-1])+triangle[i][j]\n",
    "            dp[i][i]=dp[i-1][i-1]+triangle[i][i]\n",
    "        print(dp[n-1])\n",
    "        return min(dp[n-1])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        n = len(triangle)\n",
    "        f = [[0] * n for _ in range(n)]\n",
    "        f[0][0] = triangle[0][0]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            f[i][0] = f[i - 1][0] + triangle[i][0]\n",
    "            for j in range(1, i):\n",
    "                f[i][j] = min(f[i - 1][j - 1], f[i - 1][j]) + triangle[i][j]\n",
    "            f[i][i] = f[i - 1][i - 1] + triangle[i][i]\n",
    "        \n",
    "        return min(f[n - 1])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        if not triangle or not triangle[0]:\n",
    "            return 0\n",
    "        n = len(triangle)\n",
    "        dp = [[0 for j in range(n+1)] for i in range(n)]\n",
    "        dp[0][0] = triangle[0][0]\n",
    "        res = float('inf')\n",
    "        for i in range(1,n):\n",
    "            for j in range(i+1):\n",
    "                dp[i][j] = float('inf')\n",
    "                if j == 0:\n",
    "                    # 从正上平移过来\n",
    "                     dp[i][j] = min(dp[i-1][j],dp[i][j]) + triangle[i][j]\n",
    "                elif j == i:\n",
    "                    # 从左上方面移动过来\n",
    "                     dp[i][j] = min(dp[i-1][j-1],dp[i][j]) + triangle[i][j]\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i-1][j],dp[i-1][j-1]) + triangle[i][j]\n",
    "        #print(dp)             \n",
    "        for t in range(n):\n",
    "            res = min(dp[n-1][t],res)\n",
    "        return res\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        dp = [[0] * triangle.__len__() for _ in range(triangle.__len__())]\n",
    "        dp[0][0] = triangle[0][0]\n",
    "        for i in range(1, triangle.__len__()):\n",
    "            for j in range(i + 1):\n",
    "                if j == 0:  # only come from top\n",
    "                    dp[i][j] = dp[i - 1][j] + triangle[i][j]\n",
    "                elif j == i:  # only come from top left\n",
    "                    dp[i][j] = dp[i - 1][j - 1] + triangle[i][j]\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j]\n",
    "        return min(dp[triangle.__len__() - 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        rowsNum = len(triangle)\n",
    "        dp = [[0]* i for i in range(1,rowsNum+1)]\n",
    "        dp[0][0] = triangle[0][0]\n",
    "\n",
    "        for i in range(1,rowsNum):\n",
    "            for j in range(i+1):\n",
    "                if j == 0:\n",
    "                    dp[i][j] = dp[i-1][0] + triangle[i][j]\n",
    "                elif j == i:\n",
    "                    dp[i][j] = dp[i-1][-1] + triangle[i][j]\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i-1][j],dp[i-1][j-1]) + triangle[i][j]\n",
    "        print(dp)\n",
    "        res = min(dp[-1])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        n = len(triangle)\n",
    "        dp = [[float(\"inf\")] * n for _ in range(n)]\n",
    "\n",
    "        dp[0][0] = triangle[0][0]\n",
    "        for i in range(1, n):\n",
    "            dp[i][0] = dp[i-1][0] + triangle[i][0]\n",
    "        for i in range(1, n):\n",
    "            for j in range(1, i+1):\n",
    "                dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]\n",
    "        \n",
    "        return min(dp[n-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        '''\n",
    "        记忆化搜索\n",
    "        dfs(i,j)表示位于第i层第j个数上，由此为起点得到的最小值\n",
    "        则 dfs(i,j)=t[i][j]+min(dfs(i+1,j),dfs(i+1,j+1))\n",
    "        用memo 来记忆dfs(i,j)\n",
    "        '''\n",
    "        memo = dict()\n",
    "        n = len(triangle)\n",
    "        def dfs(i,j):\n",
    "            if (i,j) in memo:\n",
    "                return memo[(i,j)]\n",
    "            if i==n-1:\n",
    "                memo[(i,j)]=triangle[i][j]\n",
    "                return triangle[i][j]\n",
    "            ans = triangle[i][j]+min(dfs(i+1,j),dfs(i+1,j+1))\n",
    "            memo[(i,j)]=ans\n",
    "            return ans\n",
    "        return dfs(0,0)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        n=len(triangle)\n",
    "        dp=[[0]*(i+1) for i in range(n)]\n",
    "        for i in range(n):\n",
    "            if i==0:\n",
    "                dp[0][0]=triangle[0][0]\n",
    "            else:\n",
    "                for j in range(i+1):\n",
    "                    if j==0:\n",
    "                        dp[i][0]=dp[i-1][0]+triangle[i][0]\n",
    "                    elif j==i:\n",
    "                        dp[i][-1]=dp[i-1][-1]+triangle[i][-1]\n",
    "                    else:\n",
    "                        dp[i][j]=min(dp[i-1][j-1],dp[i-1][j])+triangle[i][j]\n",
    "        print(dp)\n",
    "        return min(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "\n",
    "        dp = [[float('inf') for i in range(len(triangle))] for i in range(len(triangle))]\n",
    "        dp[0][0] = triangle[0][0]\n",
    "        for i in range(1, len(triangle)):\n",
    "            dp[i][0] = triangle[i][0] + dp[i-1][0]\n",
    "        for i in range(len(triangle)):\n",
    "            for j in range(1, i+1):\n",
    "                dp[i][j] = min(dp[i-1][j]+triangle[i][j], dp[i-1][j-1]+triangle[i][j])\n",
    "        print(dp)\n",
    "        return min(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        if False:\n",
    "            if len(triangle) <=1:\n",
    "                return sum(*triangle)\n",
    "\n",
    "            results = []\n",
    "\n",
    "            def dfs(paths, index):\n",
    "                if len(paths) == len(triangle):\n",
    "                    results.append(sum([i[0] for i in paths]))\n",
    "                    return\n",
    "\n",
    "                for i in range(len(triangle[index])):\n",
    "                    if not paths or (paths and (paths[-1][1] == i or paths[-1][1] == i-1)):\n",
    "                        dfs(paths + [[triangle[index][i], i]], index+1)\n",
    "                    \n",
    "            dfs([], 0)\n",
    "            print(results)\n",
    "            return min(results)\n",
    "        else:\n",
    "            grid = [[0]*(i+1) for i in range(len(triangle))]\n",
    "            print(grid)\n",
    "            for i in range(len(grid)):\n",
    "                for j in range(len(grid[i])):\n",
    "                    if i ==0 and j ==0:\n",
    "                        grid[i][j] = triangle[i][j]\n",
    "                    elif j==0:\n",
    "                        grid[i][j] = grid[i-1][j] + triangle[i][j]\n",
    "                    elif j == len(grid[i]) -1:\n",
    "                        grid[i][j] = grid[i-1][-1] + triangle[i][j]\n",
    "                    else:\n",
    "                        grid[i][j] = min(grid[i-1][j], grid[i-1][j-1]) + triangle[i][j]\n",
    "            return min(grid[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        dp=[]\n",
    "        for i in range(len(triangle)):\n",
    "            dp.append([])\n",
    "            for j in range(len(triangle[i])):\n",
    "                dp[-1].append(0)\n",
    "        \n",
    "        dp[0][0] = triangle[0][0] \n",
    "\n",
    "        for i in range(1,len(dp)):\n",
    "            for j in range(len(dp[i])):\n",
    "                if j == 0:\n",
    "                    dp[i][j] = dp[i-1][0] + triangle[i][j]\n",
    "                elif j == i:\n",
    "                    dp[i][j] = dp[i-1][i-1] + triangle[i][j]\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i-1][j-1],dp[i-1][j]) + triangle[i][j]\n",
    "        print(dp)\n",
    "        return min(dp[-1])\n",
    "\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        n = len(triangle)\n",
    "        dp = [[float('inf')]*(i+1) for i in range(1,n+1)]\n",
    "        # print(dp)\n",
    "        tmp = 0\n",
    "        for i in range(n):\n",
    "            tmp += triangle[i][0]\n",
    "            dp[i][0] = tmp\n",
    "        print(dp)\n",
    "        for i in range(1,n):\n",
    "            for j in range(1,i+1):\n",
    "                dp[i][j] = triangle[i][j] + min(dp[i-1][j],dp[i-1][j-1])\n",
    "\n",
    "        print(dp)\n",
    "        return min(dp[n-1])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            if i==m-1:\n",
    "                return triangle[i][j]\n",
    "            return triangle[i][j]+min(dfs(i+1,j),dfs(i+1,j+1))\n",
    "        m=len(triangle)\n",
    "        return dfs(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i == len(triangle):\n",
    "                return 0\n",
    "            elif not 0<=j<(len(triangle[i])):\n",
    "                return inf\n",
    "            return min(dfs(i+1, j), dfs(i+1, j+1)) + triangle[i][j]\n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        n = len(triangle[-1])\n",
    "        dp = [[0]*n for i in range(n)]\n",
    "        dp[0][0] = triangle[0][0]\n",
    "        for i in range(1,n):\n",
    "            dp[i][0] =dp[i-1][0] + triangle[i][0]\n",
    "            for j in range(1,i):\n",
    "                dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]\n",
    "            dp[i][i] = dp[i-1][i-1] + triangle[i][i]\n",
    "        print(dp)\n",
    "        return min(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        n = len(triangle)\n",
    "        dp = [[0]*(n) for _ in range(n)]\n",
    "        dp[0][0] = triangle[0][0]\n",
    "        for i in range(1, n):\n",
    "            dp[i][0] = dp[i-1][0] + triangle[i][0]\n",
    "            for j in range(1, i):\n",
    "                dp[i][j] = min(dp[i-1][j], dp[i-1][j-1]) + triangle[i][j]\n",
    "            dp[i][i] = dp[i-1][i-1] + triangle[i][i]\n",
    "        print(dp)\n",
    "        return min(dp[n-1])"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
